\documentclass[11pt]{report}

%IMPORTANTE comando \hyphenation{ma-cro-istru-zio-ne nitro-idrossil-amminico} definisce all'algoritmo di latex come spezzare una parola non presente nel suo vocabolario!!

%INCLUSIONE DI PACCHETTI
\usepackage{graphicx}
\usepackage{rotating}
\usepackage{array}
\usepackage{longtable}
\usepackage{multirow}
\usepackage{wrapfig} 
\usepackage{lastpage}
\usepackage{fancyhdr}
\usepackage[english]{babel}
\usepackage{amssymb}
%\usepackage[T1]{fontenc}
%\usepackage[latin9]{inputenc}
\usepackage[colorlinks=true]{hyperref} %per indice con link alle pagine
\usepackage[a4paper,portrait,left=2.5cm,right=2.5cm,bindingoffset=5mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{color}
%\usepackage{xstring}
\hypersetup{colorlinks,citecolor=black,filecolor=black,linkcolor=red,urlcolor=blue}
\setcounter{secnumdepth}{2} % per numerare anche \subsubsection
\setcounter{tocdepth}{2}% per farlo apparire nell'indice
\frenchspacing
\definecolor{LightMagenta}{cmyk}{0.1,0.8,0,0.1}


%HEADER e FOOTER di tutte le pagine tranne quella in cui compare il titolo del capitolo
\pagestyle{fancy}
\fancyhead{}
\headheight = 54pt
\lhead{Computer Science Theory II}
\lfoot{}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
\rhead{\nouppercase{\leftmark}}
\renewcommand{\chaptermark}[1]{\markboth{\thechapter.\ #1}{}}

%HEADER e FOOTER della pagina dove compare il titolo del capitolo
\fancypagestyle{plain}{
%\lhead{\includegraphics[height=50pt]{images/logoUniPd.png}} %IN ALTO A SINISTRA (POTREBBE ANDARE BENE IL LOGO)
\chead{}
\rhead{\bfseries WS2011/12}%\manualeUtenteVer} %IN ALTO A DESTRA
\lfoot{
\begin{tabular}{lc}
Victor A. Arrascue Ayala & Mtr. 3209050\\
Tobias Domhan  & Mtr.  3202957 \\
\end{tabular}
}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
}

\fancypagestyle{romano}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

\fancypagestyle{empty}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

%PAGINA DI PRESETAZIONE DEL DOCUMENTO
\hyphenation{}
\begin{document}


%\begin{center}
%\thispagestyle{empty}
%\huge\textbf{UNIVERSIT\`A degli Studi di PADOVA}\\[2 cm] %GRUPPO DI APPARTENENZA
%\vspace*{0.5in}
%\LARGE\textbf{Titolo del documento}\\[1.0 cm] %TITOLO DEL DOCUMENTO
%\par\rule{10cm}{.5pt} \par
%{\large 12 Ottobre 2009}   %DATA DI CREAZIONE
%\par\rule{10cm}{.10pt} \par
%\vspace*{1.0in}
%\includegraphics[scale=0.30]{images/logoUniPd.png} \\[2cm] %LOGO GRUPPO
%\Large\textbf{Michele Tonon} %AUTORE
%\par\rule{6cm}{.5pt} \par
%\end{center}



% INDEX
%\newpage
%\thispagestyle{romano}
%\pagenumbering{arabic}
%\tableofcontents


%--------------------------------------------- 


%CONTENT


\newpage
\thispagestyle{plain}

\begin{center}
{\Large \textbf{Exercise Sheet 7}}
\end{center}

\noindent{\textbf{Exercise 7.1}}\\\\
a)\\
a*b*c*\\
L = \{w $\mid$ w contains 0 or more occurrences of a, followed by 0 or more occurrences of b,  0 or more occurrences of c\}\\
Members: $\varepsilon$, abc\\
Not members: cba, bac\\
\\
b)\\
$\Sigma$*aba$\Sigma$*\\
L = \{w $\mid$ w contains \textit{aba}.\}\\
Members: aba, aaba\\
Not members: b, ab\\
\\
c)\\
((a$\cup$c)*b(a$\cup$c)*b(a$\cup$c)*b(a$\cup$c)*)*\\
L = \{w $\mid$ w is the empty string $\varepsilon$ or it contains a number of occurrences of b which is multiple of 3\}\\
Members: bbb, abcacbb\\
Not members: abc, aacc\\
\\
d)\\
b  $\cup$ b$\Sigma$*b\\
L = \{w $\mid$ w is either \textit{b} or has a \textit{b} both in the first and in the last position.\}\\
Members: b, bab\\
Not members: c, cab\\
\\

\vspace{1cm}
\noindent{\textbf{Exercise 7.2}}\\\\
a)\\
L1 = \{w $\in$ $\Sigma$* $\mid$ every 0 in w is immediately followed by a 1\}\\
((01)$\cup$1)*\\
\\
b)\\
L2 = \{w $\in$ $\Sigma$* $\mid$ the second or the third position from the end is a 1\}\\
$\Sigma$*(01 $\cup$ (1(0 $\cup$ 1)))(0 $\cup$ 1)\\
\\
\newpage
\noindent c)\\
L3 = \{w $\in$ $\Sigma$* $\mid$ w consists of alternating 0 and 1\}\\
(01)$^+$$\cup$(10)$^+$\\
The description of the language in natural language is a bit ambiguous. The following assumptions have been made: We will not accept the empty string, or either 0 or 1 alone, because it needs at least two symbols for something to alternate. Furthermore, we assume that it doesn't matter whether a word starts with 0 or with 1.\\
\\
d)\\
L4 = \{w $\in$ $\Sigma$* $\mid$ w does not contain 11\}\\
$\varepsilon$ $\cup$ 0 $\cup$ 1 $\cup$ 01 $\cup$ (0*(10)*0*)* $\cup$ (0*(10)*0*)*1\\
\\
e)\\
L5 = \{w $\in$ $\Sigma$* $\mid$ ends in even number of 0s\}\\
We assume that the empty string is part of the language, as zero is a even number.\\
$\Sigma$*1(00)*$\cup$(00)*\\
\\

\noindent{\textbf{Exercise 7.3}}\\\\
a)\\
In the following we will construct a NFA that recognizes L((30$\cup$75$\cup$45)*$\circ$10))\\
In order to do so we are using the theorems 1.45, 1.47 and 1.49, respectively("Closure under regular operations"). As well as lemma 1.55, on slide 45 ff.\\
First of all we will construct NFAs for all subexpressions: (for the sake of brevity this is only done for the subexpressions 0, 3 and 30, the other subexpressions can be transformed into a NFA analogously)\\
\begin{center}
\includegraphics[width=0.6\textwidth]{exercise7_3_subexp.pdf}
\end{center}
Next we will create a NFA, that is the union of the subexpression 30, 75 and 45:
\begin{center}
\includegraphics[width=0.7\textwidth]{exercise7_3_union.pdf}
\end{center}
Using theorem 1.49 we apply the star operation to this NFA:
\begin{center}
\includegraphics[width=0.8\textwidth]{exercise7_3_union_star.pdf}
\end{center}
Using theorem 1.47 we concatenate the above NFA with 10:
\begin{center}
\includegraphics[width=\textwidth]{exercise7_3_union_star_concate.pdf}
\end{center}

\noindent b)\\
We were not able to create a NFA with 5 states but one with 6 states (we therefore state that it is not possible to create a NFA with 5 states):
\begin{center}
\includegraphics[width=0.7\textwidth]{ex7-3b.png}
\end{center}
\end{document}

